package fullBloomFlowers;

import java.util.*;
import java.util.stream.IntStream;

public class Solution {
      public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        //
//        int max = Arrays.stream(people).max().getAsInt();
//        int[] cnt = new int[max+2];
//        for (int i = 0; i < flowers.length; i++) {
//            if(flowers[i][0] <= max) {
//                cnt[flowers[i][0]]++;
//                if(flowers[i][1] <= max) {
//                    cnt[flowers[i][1]+1]--;
//                } else {
//                    cnt[max+1]--;
//                }
//            }
//        }
//        for (int i = 1; i < cnt.length; i++) {
//            cnt[i] += cnt[i-1];
//        }
//        for (int i = 0; i < people.length; i++) {
//            people[i] = cnt[people[i]];
//        }
//        return people;

        // 差分数组

        // 超出内存问题

        // 哈希表
//        TreeMap<Integer, Integer> map = new TreeMap<>();
//        for (int i = 0; i < flowers.length; i++) {
//            int start = flowers[i][0];
//            int end = flowers[i][1];
//            map.put(start,map.getOrDefault(start,0)+1);
//            map.put(end+1,map.getOrDefault(end+1,0)-1);
//        }
//        // 遍历集合
//        int m = people.length;
//        Integer[] indices = IntStream.range(0, m).boxed().toArray(Integer[]::new);
//        Arrays.sort(indices, (i, j) -> people[i] - people[j]);
//        int[] ans = new int[m];
//        int cur = 0;
//        for(int x : indices) {
//            while (!map.isEmpty()&&map.firstKey()<=people[x]) {
//                cur+=map.pollFirstEntry().getValue();
//            }
//            ans[x] = cur;
//        }
//        return ans;

        // 二分查找
        // 找在pepal[i]之前开的花和在pepal[i]之后谢的花
        int[] start = new int[flowers.length];
        int[] end = new int[flowers.length];
        for (int i = 0; i < flowers.length; i++) {
            start[i] = flowers[i][0];
            end[i] = flowers[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        for (int i = 0; i < people.length; i++) {
            people[i] = binarySearch(start,people[i])-binarySearch(end,people[i]-1);
        }
        return people;
    }
    private int binarySearch(int[] nums,int target) {
        int l = 0,r = nums.length-1;
        while (l<=r) {
            int mid = l+(r-l)/2;
            if(nums[mid] <= target) {
                l = mid+1;
            } else {
                r = mid-1;
            }
        }
        return l;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          if(list1 == null) {
              return list2;
          } else if (list2 == null) {
              return list1;
          } else if (list1.val<list2.val) {
              ListNode ans = list1;
              ans.next = mergeTwoLists(list1.next,list2);
              return ans;
          } else {
              ListNode ans = list2;
              ans.next = mergeTwoLists(list1,list2.next);
              return ans;
          }
    }
    public ListNode removeElements(ListNode head, int val) {
          if(head == null) {
              return head;
          }
          head.next = removeElements(head.next,val);
          return head.val == val?head.next:head;
    }
//    public ListNode reverseList(ListNode head) {
//          //
//        if(head == null || head.next == null) {
//            return head;
//        }
//        ListNode ans = reverseList(head.next);
//        head.next.next = head;
//        head.next = null;
//        return ans;
//    }
    public boolean isPowerOfTwo(int n) {
          if(n%2 == 0) {
              if(n == 1) {
                  return true;
              } else if (n == 0) {
                  return false;
              }
              return isPowerOfTwo(n/2);
          } else if(n==1){
              return true;
          } else {
              return false;
          }
    }

    boolean ans = true;
    ListNode p;
    public boolean isPalindrome(ListNode head) {
        p = head;
        ans = true;
        dfs(head);
        return ans;
    }
    private void dfs(ListNode cur) {
        if(cur == null) {
            return;
        }
        dfs(cur.next);
        if(cur.val!=p.val) {
            ans = false;
        }
        p = p.next;
    }
    public boolean isPowerOfThree(int n) {
        // 3的幂
        if(n == 1) {
            return true;
        }
        if(n%3!=0) {
            return false;
        }
        if(n==0) {
            return false;
        }
        return isPowerOfThree(n/3);
    }
    public boolean isPowerOfFour(int n) {
        if(n == 1) {
            return true;
        }
        if(n%4!=0) {
            return false;
        }
        if(n == 0) {
            return false;
        }
        return isPowerOfFour(n/4);
    }
    public ListNode reverseList(ListNode head) {
        if(head == null||head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
    public int[] reverseBookList(ListNode head) {
        List<Integer> list = new ArrayList<>();
        dfs(list,head);
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
    private void dfs(List<Integer> list,ListNode cur){
        if(cur == null) {
            return;
        }
        dfs(list,cur.next);
        list.add(cur.val);
    }
    public ListNode trainningPlan(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode p = trainningPlan(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        //
        if(l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = trainningPlan(l1.next,l2);
            return l1;
        } else {
            l2.next = trainningPlan(l1,l2.next);
            return l2;
        }
    }
    public int iceBreakingGame(int num, int target) {
        return f(num, target);
    }
    public int f(int num, int target) {
        if (num == 1) {
            return 0;
        }
        int x = f(num - 1, target);
        return (target + x) % num;
    }

//    public int fib(int n) {
//        if (n < 2) {
//            return n;
//        }
//        int[][] q = {{1, 1}, {1, 0}};
//        int[][] res = pow(q, n - 1);
//        return res[0][0];
//    }
//    public int[][] pow(int[][] a, int n) {
//        int[][] ret = {{1, 0}, {0, 1}};
//        while (n > 0) {
//            if ((n & 1) == 1) {
//                ret = multiply(ret, a);
//            }
//            n >>= 1;
//            a = multiply(a, a);
//        }
//        return ret;
//    }
//    public int[][] multiply(int[][] a, int[][] b) {
//        int[][] c = new int[2][2];
//        for (int i = 0; i < 2; i++) {
//            for (int j = 0; j < 2; j++) {
//                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
//            }
//        }
//        return c;
//    }
}
